package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-05-05 10:48
 */
public class LongestIncreasingSubsequence {
    /**leetcode 674
     * 五部曲：dp[i]:以dp[i]为结尾元素的递增序列 递推公式：dp[i]=max(dp[i],dp[j]) 初始化 所有的元素均初始化为1 （最少是一个元素）
     * 遍历顺序：从前往后即可
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        //创建dp数组并初始化
        int[]dp=new int[nums.length];
        for(int i=0;i<nums.length;++i){
            dp[i]=1;
        }
        //递推公式
        int max=1;
        for(int i=1;i<nums.length;++i){
            for(int j=0;j<i;++j){
                if(nums[i]>nums[j]&&dp[i]<(dp[j]+1)){
                    dp[i]=dp[j]+1;
                }
            }
            if(dp[i]>max){
                max=dp[i];
            }
        }

        return max;
    }
}
